package com.dy.分类.二分查找和二叉排序树.在排序数组中查找元素的第一个和最后一个位置34;

public class Solutioin {
    public int[] searchRange(int[] nums, int target) {
        int res[] = new int[]{-1, -1};
        int start = 0;
        int end = nums.length - 1;
        int mid = 0;
        while (start <= end) {
            mid = start + (end - start) / 2;
            if (nums[mid] == target) {
                int i = mid, j = mid;
                while (i > 0 && nums[i - 1] == target) {
                    i--;
                }
                while (j < nums.length - 1 && nums[j + 1] == target){
                    j++;
                }
                res[0]=i;
                res[1]=j;
                return res;
            }
            else if(nums[mid]>target){
                end = mid-1;

            }else{
                start = mid+1;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        Solutioin solutioin = new Solutioin();
        int res[] = new int[2];
        res =solutioin.searchRange2(new int[]{5,7,7,8,8,8,10},5);
        System.out.println(res[0]+" "+ res[1]);
    }

    public int[] searchRange2(int[] nums, int target) {
        int res[] = new int[]{-1,-1};
        int a = search(nums,target-0.5);
        int b = search(nums,target+0.5);
        if(a==b){
            return res;
        }
        res[0] = a;
        res[1] = b-1;
        return res;
    }
    public int search(int[] nums, double target) {
        int start = 0;
        int end = nums.length - 1;
        int mid = 0;
        while (start <= end) {
            mid = start + (end - start) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            else if(nums[mid]>target){
                end = mid-1;

            }else{
                start = mid+1;
            }
        }
        return start;
    }
}
